package com.foxzzz.temporary;

public class Solution99 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    private TreeNode preNode = null;
    private TreeNode firstErrorNode = null;
    private TreeNode secondErrorNode = null;

    public void inorder(TreeNode treeNode) {
        if (treeNode == null)
            return;
        // 两类有问题的节点
        // 第一类节点的特征是它的值比后面的大，记为A，
        // 第二类节点的特征是它的值比前面的小，记为B
        // 1.如果是相领的节点交换，就会出现...A, B, ...
        // 2.如果是首尾节点交换，就会出现A, ..., B
        // 3.如果不相领的节点交换，就会出现..., A1, B1, ..., A2, B2, ...
        // 其中交换的节点是A1,B2
        // 所以，只需要交换第一个A型节点和最后一个B型节点

        inorder(treeNode.left);
        if (preNode != null && treeNode.val < preNode.val) {
            if (firstErrorNode == null)
                firstErrorNode = preNode; // 只保存第一个A
            //find second one
            secondErrorNode = treeNode; // 保存每一个B，就是最后一个
        }
        preNode = treeNode;
        inorder(treeNode.right);

    }

    public void recoverTree(TreeNode root) {
        inorder(root);
        int temp = 0;
        temp = firstErrorNode.val;
        firstErrorNode.val = secondErrorNode.val;
        secondErrorNode.val = temp;
    }

    public void test() {
        // 3 2 1
        //1 3 2 4
        //1 6 3 4 5 2 7
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(3);
        TreeNode t3 = new TreeNode(2);
        t1.left = t2;
        t1.right = null;
        t2.left = null;
        t2.right = t3;
        recoverTree(t1);

    }

    public static void main(String[] args) {
        new Solution99().test();
    }

}
